package 算法.排序.堆排序;

import java.util.Random;

import util.LogUtils;

/**
 * 堆排序Demo1：
 * 	
 */
public class HeapDemo1 {
	
	public static void main(String[] args) {
		Random random = new Random();
		//数组第一个元素不用
		Integer[] arr = {-1, 8, 7, 6, 5, 4};
		//将索引为5(4)进行swim
//		sink(arr, 1, 5);
		sort(arr);
		print(arr);
	}
	
    public static void sort(Integer[] arr) {
        int n = arr.length;

       for (int k = n; k >= 1; k --) 
////        for (int k = n/2; k >= 1; k--)		//书上介绍更高级的方法
            sink(arr, k, n);
       
//        while (n > 1) {
//            swap(arr, 1, n--);
//            sink(arr, 1, n);
//        }
       LogUtils.print(arr);
    }
	
	/**
	 * 上浮:
	 * 	将其/2
	 */
	public static void swim(Integer[] arr, int target, int N) {
		while(target > 1) {
			int k = target / 2;
			if(arr[k] < arr[target]) {
				swap(arr, k, target);
			}
			target = k;
			
		}
	}
	//和上面一样的  （书上标准）
	public static void swim(int[] arr, int target) {
//		while (target > 1 
//					&& arr[target/2]<arr[target]) {
//			swap(arr, target, target/2);
//			target = target / 2;
//		}
	}
	
	
	/**	目标：小顶堆       k*2 或 k*2+1
	 * @param arr
	 * @param k		需要sink的元素索引
	 * @param N		数组总长度 
	 */
	public static void  sink(Integer[] arr, int k, int N) {
		while(k*2 <= N) {					//在这里数组从1开始 
			int j = k * 2;
			/*
			 * 因为数组长度+1 所以索引全部要-1
			 */
			if (j<N && arr[j-1]<arr[j-1+1]) j++;
			if (arr[j-1]<arr[k-1]) break;  		//如果当前节点已经比子节点小了，就不用交换了
			swap(arr, j, k);
			k = j;
		}
		//书上标准
//        while (2*k <= N) {
//            int j = 2*k;
//            if (j < N && less(arr, j, j+1)) j++;
//            if (!less(arr, k, j)) break;
//            swap(arr, k, j);
//            k = j;
//        }
	}
	
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }
	
	public static void swap(Integer[] arr, int a, int b) {
		int t = arr[a-1];
		arr[a-1] = arr[b-1];
		arr[b-1] = t;
	}
	
	public static void print(Integer[] arr) {
		for (int value : arr) {
			System.out.print(value+"..");
		}
	}
}
